package leetcode.editor.cn.dsa20_heap;
//给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
// 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。
// 找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class FindKPairsWithSmallestSums373_2 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<List<Integer>> result = new ArrayList<>();
            if (nums1.length == 0 || nums2.length == 0) return result;
            // 存入的是坐标，方便得到堆顶元素的下一组元素
            PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
                return nums1[o1[0]] + nums2[o1[1]] - (nums1[o2[0]] + nums2[o2[1]]);
            });
            // 维护一个大小为k的小顶堆，将某个升序序列加入
            for (int i = 0; i < Math.min(nums1.length, k); i++) {
                queue.offer(new int[]{i, 0});
            }
            while (k-- > 0 && !queue.isEmpty()) {
                int[] pair = queue.poll(); // 弹出堆顶元素
                List<Integer> item = new ArrayList<>();
                item.add(nums1[pair[0]]);
                item.add(nums2[pair[1]]);
                // 加入堆顶元素的下一组元素，即相邻元素
                if (pair[1] < nums2.length - 1) {
                    queue.offer(new int[]{pair[0], pair[1] + 1});
                }
                result.add(item);
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}